lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Adequate systems of connectives.md (580B)

      1 +++
      2 title = 'Adequate systems of connectives'
      3 +++
      4 # Adequate systems of connectives
      5 a system C of connectives is adequate if every truth table can be expressed as formula with connectives C
      6 
      7 example:
      8 express (p ∧ ¬ q) ∨ (¬ p ∧ q) in the system {¬, ∧}
      9 
     10 - use: ϕ ∨ Ψ ≡ ¬ (¬ ϕ ∧ ¬ Ψ)
     11 - rewrite like hell
     12 - result: ¬ (¬ p ∨ ¬¬ q) ∨ ¬ (¬ ¬ p ∨ ¬ q)
     13 
     14 Sheffer stroke is an adequate system — {|}
     15 - ϕ | Ψ means "not both ϕ and Ψ” (ϕ NAND Ψ)
     16 - ϕ | Ψ ≡ ¬ (ϕ ∧ Ψ)
     17 
     18 adequate systems are: {|}, {¬, ∧}, {¬, ∨}, {¬, ∧, ∨}, etc.